package com.feiyu.simplesort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author feiyu127
 * @date 2017/10/29 14:08
 * @desc
 */

public class MergeSort extends BaseSort {

    @Override
    public int[] sort(int[] array) {
        return mergeSort2(array, 0, array.length);
//        return mergeSort(array);
    }

    private int[] mergeSort(int[] array) {
        int length = array.length;
        if (length == 1) {
            return array;
        }
        int first = length / 2;
        int[] array1 = mergeSort(Arrays.copyOfRange(array, 0, first));
        int[] array2 = mergeSort(Arrays.copyOfRange(array, first, length));
        int[] result = merge(array1, array2);
        System.arraycopy(result, 0, array, 0, array.length);
        return array;
    }

    private int[] merge(int[] array1, int[] array2) {
        int len1 = array1.length;
        int len2 = array2.length;
        int[] array = new int[len1 + len2];
        int i = 0, j = 0, k = 0;
        while (i < len1 && j < len2) {
            if (array1[i] > array2[j]) {
                array[k++] = array2[j++];
            } else {
                array[k++] = array1[i++];
            }
        }
        if (i < len1) {
            System.arraycopy(array1, i, array, k, len1 - i);
        } else {
            System.arraycopy(array2, j, array, k, len2 - j);
        }
        return array;
    }

    private int[] mergeSort2(int[] array, int start1, int end) {
        int length = end - start1;
        if (length == 1) {
            return array;
        }
        int start2 = (start1 + end) /2;
        mergeSort2(array, start1, start2);
        mergeSort2(array, start2, end);
        return array;
    }

    private void merge2(int[] array, int start1, int start2, int end) {
        int len1 = start2 - start1;
        int len2 = end - start2;
        int[] array1 = Arrays.copyOfRange(array, start1, start2);
        int[] array2 = Arrays.copyOfRange(array, start2, end);
        int i = 0, j = 0, k = start1;
        while (i < len1 && j < len2) {
            if (array1[i] > array2[j]) {
                array[k++] = array2[j++];
            } else {
                array[k++] = array1[i++];
            }
        }
        if (i < len1) {
            System.arraycopy(array1, i, array, k, len1 - i);
        } else {
            System.arraycopy(array2, j, array, k, len2 - j);
        }

    }
}
